//
// Created by lanlu on 2025/8/7.
//

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};


class Solution {
public:
    // 存储中序遍历中的值和索引
    unordered_map<int,int> um;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         for (int i = 0; i < inorder.size(); i++)
         {
             um[inorder[i]] = i;
         }
         return buildTreeByRec(preorder, 0, preorder.size() - 1,
             inorder, 0, inorder.size() - 1);

    }

    TreeNode * buildTreeByRec(vector<int> &preorder, int preStart, int preEnd,
                             vector<int> &inorder, int inStart, int inEnd)
    {
        // 递归出口
        if (preStart > preEnd || inStart > inEnd)
        {
            return nullptr;
        }

        // 递归规律
        int rootVal = preorder[preStart];
        TreeNode *root = new TreeNode(rootVal);

        // 查找根节点在中序遍历中的索引
        int rootIndex = um[rootVal];
        int leftSize = rootIndex - inStart;

        // 注意这里是左闭右闭的区间
        root->left = buildTreeByRec(preorder, preStart + 1, preStart + leftSize,
                                    inorder, inStart, rootIndex - 1);

        root->right = buildTreeByRec(preorder, preStart + leftSize + 1, preEnd,
                                     inorder, rootIndex + 1, inEnd);
        return root;
    }
};
